package org.codetranslators.common;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.Vector;

public class SpanningTreeDFS extends DepthFirstSearch{
	
	private SpanningTreeNode spanningTreeRoot;
	private HashMap edgeVsVisitStatus;
	private HashMap nodeVsSpanningTreeNode;
	
	private Vector backEdges;
	private Vector visitedNodes;
	
	private int currentDepthNumber;
	
	public Object execute(DiGraph graph, Node startNode){
		super.execute(graph, startNode);
		currentDepthNumber = 1;
		
		edgeVsVisitStatus = new HashMap();
		nodeVsSpanningTreeNode = new HashMap();
		backEdges = new Vector();
		visitedNodes = new Vector();
		
		int numNodes = graph.getNumNodes();
		for(int i = 0; i < numNodes; i++)
		{
			Node node = graph.getNode(i);
			TreeNode treeNode = new TreeNode(node.getName());
			SpanningTreeNode spanningTreeNode = new SpanningTreeNode(treeNode, node);
			spanningTreeNode.setVisited(false);
			if(node == startNode)
			{
				spanningTreeNode.setDepthNumber(currentDepthNumber);
				spanningTreeRoot = spanningTreeNode;
				visitedNodes.addElement(spanningTreeNode);
			}
			nodeVsSpanningTreeNode.put(node, spanningTreeNode);
		}
		
		int numEdges = graph.getNumEdges();
		for(int i = 0; i < numEdges; i++)
		{
			Boolean visited = new Boolean(false);
			Edge edge = graph.getEdge(i);
			edgeVsVisitStatus.put(edge, visited);
		}
		
		return traverse(startNode);
	}
	
	public boolean isVisited(Edge edge) {
		Boolean visited = (Boolean) edgeVsVisitStatus.get(edge);
		return visited.booleanValue();
	}
	
	public boolean isVisited(Node node){
		SpanningTreeNode spanningTreeNode = (SpanningTreeNode) nodeVsSpanningTreeNode.get(node);
		return spanningTreeNode.isVisited();
	}
	
	public void visit(Edge edge){
		edgeVsVisitStatus.put(edge, new Boolean(true));
	}
	
	public void visit(Node node){
		SpanningTreeNode spanningTreeNode = (SpanningTreeNode) nodeVsSpanningTreeNode.get(node);
		spanningTreeNode.setVisited(true);		
	}
	
	public boolean isDone(){
		return false;
	}
	
	public void traverseDiscovery(Node nextNode, Node node){
		SpanningTreeNode stNode = (SpanningTreeNode)nodeVsSpanningTreeNode.get(node);
		
		SpanningTreeNode stNodeNext = (SpanningTreeNode)nodeVsSpanningTreeNode.get(nextNode);
		stNodeNext.setDepthNumber(++currentDepthNumber);
		stNodeNext.setName(nextNode.getName());
		
		stNode.addChild(stNodeNext);
		
		visitedNodes.addElement(stNodeNext);
	}
	
	public void traverseBack(Edge edge, Node node){
		backEdges.addElement(edge);
	}
	
	/**
	 * This function creates the spanning tree and returns it.
	 */
	public Object getResult(){
		SpanningTree spanningTree = new SpanningTree();
		spanningTree.setGraphNodeVsSpanningTreeNode(nodeVsSpanningTreeNode);
		spanningTree.setVisitedNodes(visitedNodes);
		spanningTree.setSpanningTreeRoot(spanningTreeRoot);
		return spanningTree;
	}
	
	public Vector getBackEdges(){
		return backEdges;
	}
}
